package LeetCode;

import java.util.*;

public class LC_199_BinaryTreeRightSideView {

    public static void main(String[] args) {

    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    static class Solution {
        public List<Integer> rightSideView(TreeNode root) {
            Stack<TreeNode> stack = new Stack<>();
            Stack<TreeNode> stack1 = new Stack<>();
            List<Integer> list = new ArrayList<>();
            TreeNode current = root;
            int curHeight = 1;
            int rightHeight = 0;
            while (current != null || !stack.isEmpty()) {
                if (current != null) {
                    if (curHeight > rightHeight) list.add(current.val);
                    stack.push(current);
                    stack1.push(current);
                    current = current.right;
                    ++curHeight;
                } else {
                    current = stack.pop();
                    while (!stack1.isEmpty()) {
                        if (stack1.peek() == current) {
                            curHeight = stack1.size();
                            if (curHeight > rightHeight) rightHeight = curHeight;
                            break;
                        }
                        stack1.pop();
                    }
                    current = current.left;
                    ++curHeight;
                }
            }
            return list;
        }
    }

    static class Solution_2 {
        public List<Integer> rightSideView(TreeNode root) {
            List<Integer> list = new ArrayList<>();
            if (root == null) return list;
            Queue<TreeNode> queue = new LinkedList<>();
            TreeNode current = root;
            queue.offer(current);
            queue.offer(null);
            while (!queue.isEmpty()) {
                current = queue.poll();
                if (current != null) {
                    if (queue.peek() == null) list.add(current.val);
                    if (current.left != null) queue.add(current.left);
                    if (current.right != null) queue.add(current.right);
                } else {
                    if (queue.isEmpty())
                        break;
                    else
                        queue.add(null);
                }
            }
            return list;
        }
    }

}